googologywikiaorg-20200223-history
Slow-growing hierarchy
The slow-growing hierarchy (SGH) is a certain hierarchy mapping ordinals \(\alpha\) to functions \(g_\alpha: \mathbb{N} \rightarrow \mathbb{N}\). Like its name suggests, it grows much slower than its cousins the fast-growing hierarchy and the Hardy hierarchy. The functions are defined as follows: * \(g_0(n) = 0\) * \(g_{\alpha+1}(n) = g_\alpha(n)+1\) * \(g_\alpha(n) = g_{\alphan}(n)\) iff \(\alpha\) is a limit ordinal \(\alphan\) denotes the \(n\)th term of the fundamental sequence assigned to ordinal \(\alpha\). Definitions of \(\alphan\) can vary, giving different slow-growing hierarchies. One such hierarchy is the Wainer hierarchy, which is explained in the article for fast-growing hierarchy. For small ordinals, SGH is nowhere close to FGH. \(g_{\epsilon_0}(n)\) only reaches the level of \(f_3(n)\), and SGH does not reach \(f_{\varepsilon_0}(n)\) until the Bachmann-Howard ordinal. Unlike its relatives, SGH is extremely sensitive to the definitions of fundamental sequences; in one version SGH catches up FGH at \(\psi_0(\Omega_\omega)\). To googologists, SGH is not quite as useful as FGH. It grows the slowest of all the ordinal hierarchies, so it may be the best suited to stratify the growth rates of functions. Interestingly, it occurs naturally in BEAF; if the pilot is at position \(\alpha\), the number of entries in the prime block is \(g_{\alpha}(p)\). Functions Below is the list of comparisons between SGH and other googological notations. Up to \(\Gamma_0\) \(g_0(n) = 0\) \(g_m(n) = m\) \(g_\omega(n) = n\) \(g_{\omega^{\omega}}(n) = n^n\) \(g_{\varepsilon_0}(n) = n \uparrow\uparrow n\) \(g_{\varepsilon_1}(n) \approx n \uparrow\uparrow n+1\) \(g_{\varepsilon_2}(n) \approx n \uparrow\uparrow n+2\) \(g_{\varepsilon_{\omega}}(n) \approx n \uparrow\uparrow 2n\) \(g_{\varepsilon_{\omega^2}}(n) \approx n \uparrow\uparrow n(n+1)\) \(g_{\varepsilon_{\omega^3}}(n) \approx n \uparrow\uparrow n^3\) \(g_{\varepsilon_{\omega^{\omega}}}(n) \approx n \uparrow\uparrow (n^n)\) \(g_{\varepsilon_{\varepsilon_0}}(n) \approx n \uparrow\uparrow (n \uparrow\uparrow n)\) \(g_{\zeta_0}(n) \approx n \uparrow\uparrow\uparrow n\) \(g_{\varepsilon_{\zeta_0+1}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow n\) \(g_{\varepsilon_{\zeta_0+2}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow (2n)\) \(g_{\varepsilon_{\zeta_0 2}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow (n \uparrow\uparrow\uparrow n) \approx n \uparrow\uparrow\uparrow (n+1)\) \(g_{\varepsilon_{\zeta_0 3}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow (2(n \uparrow\uparrow\uparrow n))\) \(g_{\varepsilon_{\zeta_0 4}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow (3(n \uparrow\uparrow\uparrow n))\) \(g_{\varepsilon_{\zeta_0 \omega}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow (n(n \uparrow\uparrow\uparrow n))\) \(g_{\varepsilon_{\zeta_0^2}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow ({(n \uparrow\uparrow\uparrow n)}^2)\) \(g_{\varepsilon_{\zeta_0^{\zeta_0}}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow ({(n \uparrow\uparrow\uparrow n)}^{n \uparrow\uparrow\uparrow n})\) \(g_{\varepsilon_{\varepsilon_{\zeta_0}}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow ((n \uparrow\uparrow\uparrow n) \uparrow\uparrow n)\) \(g_{\varepsilon_{\varepsilon_{\zeta_0 2}}}(n) \approx (n \uparrow\uparrow\uparrow n) \uparrow\uparrow ((n \uparrow\uparrow\uparrow n) \uparrow\uparrow (n \uparrow\uparrow\uparrow n)) \approx n \uparrow\uparrow\uparrow (n+2)\) \(g_{\zeta_1}(n) \approx n \uparrow\uparrow\uparrow 2n\) \(g_{\zeta_2}(n) \approx n \uparrow\uparrow\uparrow 3n\) \(g_{\zeta_\omega}(n) \approx n \uparrow\uparrow\uparrow n^2\) \(g_{\zeta_{\omega^\omega}}(n) \approx n \uparrow\uparrow\uparrow n^n\) \(g_{\zeta_{\varepsilon_0}}(n) \approx n \uparrow\uparrow\uparrow (n \uparrow\uparrow n)\) \(g_{\zeta_{\varepsilon_{\varepsilon_0}}}(n) \approx n \uparrow\uparrow\uparrow (n \uparrow\uparrow (n \uparrow\uparrow n))\) \(g_{\zeta_{\zeta_0}}(n) \approx n \uparrow\uparrow\uparrow (n \uparrow\uparrow\uparrow n)\) \(g_{\zeta_{\zeta_{\zeta_0}}}(n) \approx n \uparrow\uparrow\uparrow n \uparrow\uparrow\uparrow n \uparrow\uparrow\uparrow n\) \(g_{\eta_0}(n) \approx n \uparrow\uparrow\uparrow\uparrow n\) \(g_{\varepsilon_{\eta_0+1}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow n\) \(g_{\varepsilon_{\eta_0+2}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow n+1\) \(g_{\varepsilon_{\eta_0+\omega}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow 2n\) \(g_{\varepsilon_{\eta_0+\omega^\omega}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow n^n\) \(g_{\varepsilon_{\eta_0+\varepsilon_0}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow n \uparrow\uparrow n\) \(g_{\varepsilon_{\eta_0+\varepsilon_{\varepsilon_0}}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow n \uparrow\uparrow n \uparrow\uparrow n\) \(g_{\varepsilon_{\eta_0+\zeta_0}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow\uparrow n\) \(g_{\varepsilon_{\eta_0+\zeta_1}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow\uparrow n+1\) \(g_{\varepsilon_{\eta_0+\zeta_\omega}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow\uparrow 2n\) \(g_{\varepsilon_{\eta_0+\zeta_{\omega^\omega}}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow\uparrow n^n\) \(g_{\varepsilon_{\eta_0+\zeta_{\zeta_0}}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow\uparrow n \uparrow\uparrow\uparrow n\) \(g_{\varepsilon_{\eta_02}}(n) \approx (n \uparrow\uparrow\uparrow\uparrow n) \uparrow\uparrow\uparrow\uparrow n\) \(g_{\varphi(4,0)}(n) \approx n \uparrow\uparrow\uparrow\uparrow\uparrow n\) \(g_{\varphi(5,0)}(n) \approx n \uparrow\uparrow\uparrow\uparrow\uparrow\uparrow n\) \(g_{\varphi(\omega,0)}(n) \approx \{n,n,n+1\}\) \(g_{\varphi(\omega^\omega,0)}(n) \approx \{n,n,n^n+1\}\) \(g_{\varphi(\varepsilon_0,0)}(n) \approx \{n,n,n \uparrow\uparrow n+1\}\) \(g_{\varphi(\zeta_0,0)}(n) \approx \{n,n,n \uparrow\uparrow\uparrow n+1\}\) \(g_{\varphi(\eta_0,0)}(n) \approx \{n,n,n \uparrow\uparrow\uparrow\uparrow n+1\}\) \(g_{\varphi(\varphi(\omega,0),0)}(n) \approx \{n,n,\{n,n,n+1\}+1\}\) \(g_{\varphi(\varphi(\varphi(\omega,0),0),0)}(n) \approx \{n,n,\{n,n,\{n,n,n+1\}+1\}+1\}\) Beyond \(\Gamma_0\) \(g_{\Gamma_0}(n) \approx \{n,n,1,2\}\) \(g_{\varphi(\Gamma_0,1)}(n) \approx \{n,n+1,1,2\}\) \(g_{\varphi(\varphi(\Gamma_0,1),0)}(n) \approx \{n,n+2,1,2\}\) \(g_{\Gamma_1}(n) \approx \{n,2n,1,2\}\) \(g_{\Gamma_2}(n) \approx \{n,3n,1,2\}\) \(g_{\Gamma_\omega}(n) \approx \{n,(n+1)n,1,2\}\) \(g_{\Gamma_{\omega^2}}(n) \approx \{n,(n^2+1)n,1,2\}\) \(g_{\Gamma_{\omega^\omega}}(n) \approx \{n,(n^{n-1}+1)n,1,2\}\) \(g_{\Gamma_{\omega^{\omega^\omega}}}(n) \approx \{n,(n^{n^n-1}+1)n,1,2\}\) \(g_{\Gamma_{\varepsilon_0}}(n) \approx \{n,n \uparrow\uparrow n,1,2\}\) \(g_{\Gamma_{\zeta_0}}(n) \approx \{n,n \uparrow\uparrow\uparrow n,1,2\}\) \(g_{\Gamma_{\eta_0}}(n) \approx \{n,n \uparrow\uparrow\uparrow\uparrow n,1,2\}\) \(g_{\Gamma_{\varphi(\omega,0)}}(n) \approx \{n,\{n,n,n+1\},1,2\}\) \(g_{\Gamma_{\Gamma_0}}(n) \approx \{n,\{n,n,1,2\},1,2\}\) \(g_{\Gamma_{\Gamma_{\Gamma_0}}}(n) \approx \{n,\{n,\{n,n,1,2\},1,2\},1,2\}\) \(g_{\varphi(1,1,0)}(n) \approx \{n,n,2,2\}\) \(g_{\varphi(1,2,0)}(n) \approx \{n,n,3,2\}\) \(g_{\varphi(1,\omega,0)}(n) \approx \{n,n,n,2\}\) \(g_{\varphi(1,\Gamma_0,0)}(n) \approx \{n,n,\{n,n,1,2\},2\}\) \(g_{\varphi(1,\varphi(1,\Gamma_0,0),0)}(n) \approx \{n,n,\{n,n,\{n,n,1,2\},2\},2\}\) \(g_{\varphi(2,0,0)}(n) \approx \{n,n,1,3\}\) \(g_{\varphi(3,0,0)}(n) \approx \{n,n,1,4\}\) \(g_{\varphi(\omega,0,0)}(n) \approx \{n,n,1,n+1\}\) \(g_{\varphi(\Gamma_0,0,0)}(n) \approx \{n,n,1,\{n,n,1,2\}+1\}\) \(g_{\varphi(1,0,0,0)}(n) \approx \{n,n,1,1,2\}\) \(g_{\varphi(1,0,0,0,0)}(n) \approx \{n,n,1,1,1,2\}\) \(g_{\varphi(1,0,0,0,0,0)}(n) \approx \{n,n,1,1,1,1,2\}\) \(g_{\vartheta(\Omega^\omega)}(n) \approx \{n,n+2 (1) 2\}\) \(g_{\vartheta(\omega\Omega^\omega)}(n) \approx \{n,n+2 (1) n\}\) \(g_{\vartheta(\varepsilon_0\Omega^\omega)}(n) \approx \{n,n+2 (1) n \uparrow\uparrow n\}\) \(g_{\vartheta(\Omega^{\omega+1})}(n) \approx \{n,n (1) 1,2\}\) \(g_{\vartheta(\Omega^{\omega+1})}(n) \approx \{n,n (1) 1,1,2\}\) \(g_{\vartheta(\Omega^{\omega 2})}(n) \approx \{n,n (1)(1) 2\}\) \(g_{\vartheta(\Omega^{\omega 3})}(n) \approx \{n,n (1)(1)(1) 2\}\) \(g_{\vartheta(\Omega^{\omega^2})}(n) \approx \{n,n (2) 2\}\) \(g_{\vartheta(\Omega^{\omega^3})}(n) \approx \{n,n (3) 2\}\) \(g_{\vartheta(\Omega^{\omega^\omega})}(n) \approx \{n,n (0,1) 2\}\) Category:Hierarchies